package dac;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上
 * (即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
 * (1) 每次只能移动一个盘子;
 * (2) 盘子只能从柱子顶端滑出移到下一根柱子;
 * (3) 盘子只能叠在比它大的盘子上。
 *
 * 用栈将所有盘子从第一根柱子移到最后一根柱子。
 *
 */
public class DacHanNt {
    public static void main(String[] args) {
        List<Integer> a = new ArrayList();
        a.add(0);a.add(1);a.add(2);
        System.out.println(a);
        List<Integer> c = new ArrayList<>();
        hanota(a,new ArrayList<>(),c);
        System.out.println(c);
    }
    /**
     *
     *
     * @param A
     * @param B
     * @param C
     * (1) 每次只能移动一个盘子;
     * (2) 盘子只能从柱子顶端滑出移到下一根柱子;
     * (3) 盘子只能叠在比它大的盘子上。
     */
    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(),A,B,C);
    }

    /**
     * 1.只有一个盘 A->C
     * 2.有2个盘 A->B A->C B->A 先把上面挪到B 然后再把最下面的A挪到C 再把B挪到C
     * 3.n 个盘子 可以看作 n-1 放在b 最后一个放 C 再把N-1 挪到C
     * @param num
     * @param A
     * @param B
     * @param C
     */
    public static void move(int num, List<Integer> A, List<Integer> B, List<Integer> C){
        if(num == 1){
            C.add( A.remove(A.size()-1));
        }else {
            move(num-1, A, C, B); // 将A上面n-1个通过C移到B
            C.add(A.remove(A.size()-1));
            move(num-1, B, A, C); // 将B上面n-1个通过空的A移到C
        }
    }



}
